

// 第三大的数
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        set<int> s;
        for(int x : nums)
        {
            s.insert(x);
            if(s.size() > 3)
                s.erase(s.begin());
        }
        return s.size() == 3 ? *s.begin() : *s.rbegin();
    }
};


//最大连续1的个数 III
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int ret = 0;
        for(int left = 0, right = 0, count = 0; right < nums.size(); right++)
        {
            if(nums[right] == 0)
                ++count;
            while(count > k)
            {
                if(nums[left++] == 0)
                    --count;
            }
            if(right - left + 1 > ret)
                ret = right - left + 1;
        }
        return ret;
    }
};


//最长重复子数组
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        int ret;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(nums1[i - 1] == nums2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ret = max(ret, dp[i][j]); 
                }
            }
        }
        return ret;
    }
};



//单词拆分
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> set;
        for(auto str : wordDict)
            set.insert(str);
        int n = s.size();
        vector<bool> dp(n + 1);
        dp[n] = true;

        for(int i = n - 1; i >= 0; i--)
        {
            for(auto w : set)
            {
                int len = w.size();
                if(i + len > n)
                    continue;
                if(s.substr(i, len) == w && dp[i + len])
                    dp[i] = true;

            }
        }
        return dp[0];
    }
};


//最长等差子序列
class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
     int n = nums.size();
     unordered_map<int, int> hash;
     hash[nums[0]] = 0;
     vector<vector<int>> dp(n, vector<int>(n, 2));
     int ret = 2;
     for(int i = 1; i < n; i++)
     {
        for(int j = i + 1; j < n; j++)
        {
            int a = 2 * nums[i] - nums[j];
            if(hash.count(a))
                dp[i][j] = dp[hash[a]][i] + 1;
            ret = max(ret, dp[i][j]);
        }
        hash[nums[i]] = i;
     }
     return ret;
    }
};



//俄罗斯套娃信封
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(),[](const auto& e1, const auto& e2){
            if(e1[0] == e2[0])
                return e1[1] > e2[1];
            return e1[0] < e2[0];
        });
    
        vector<int> dp;
        dp.push_back(envelopes[0][1]);
        for(auto& e : envelopes)
        {
            if(dp.back() < e[1])
                dp.push_back(e[1]);
            else
            {
                auto it = lower_bound(dp.begin(), dp.end(), e[1]);
                *it = e[1];
            }
        }
        return dp.size();
    }
};
